package club.xiaojiawei.array;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/14/22 11:16 PM
 * @question
 * @description
 */
public class SmallerNumbersThanCurrent1365 {

    public static void main(String[] args) {
        SmallerNumbersThanCurrent1365 test = new SmallerNumbersThanCurrent1365();
        int[] result = test.smallerNumbersThanCurrent3(new int[]{6, 5, 4, 8});
        System.out.println(Arrays.toString(result));
    }

    /**
     * 朴素法
     * @param nums
     * @return
     */
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i];
            for (int num : nums) {
                if (temp > num){
                    result[i]++;
                }
            }
        }
        return result;
    }

    /**
     * 官方-排序
     * 时间复杂度 O(NlogN)
     * 空间复杂度 O(N)
     * @param nums
     * @return
     */
    public int[] smallerNumbersThanCurrent2(int[] nums) {
        int n = nums.length;
        int[][] data = new int[n][2];
        for (int i = 0; i < n; i++) {
            data[i][0] = nums[i];
            data[i][1] = i;
        }
        Arrays.sort(data, Comparator.comparingInt(data2 -> data2[0]));
        int[] ret = new int[n];
        int prev = -1;
        for (int i = 0; i < n; i++) {
            if (prev == -1 || data[i][0] != data[i - 1][0]) {
                prev = i;
            }
            ret[data[i][1]] = prev;
        }
        return ret;
    }

    /**
     * 练习-计数排序
     * 时间复杂度O(N+K)
     * 空间复杂度O(K)
     * @param nums
     * @return
     */
    public int[] smallerNumbersThanCurrent3(int[] nums) {
        int[] arr = new int[101];
        for (int num : nums) {
            arr[num]++;
        }
        for (int i = 1; i <= 100; i++) {
            arr[i] += arr[i - 1];
        }
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = nums[i] == 0? 0 : arr[nums[i] - 1];
        }
        return result;
    }
}
